package letcode.oneQuestionPerDay._202004._20;

import java.util.*;

/**
 * @Description: 岛屿数量
 * @Date: 2020/4/20
 * @Author: 许群星
 */
public class IslandNumbers_b {
    public static void main(String[] args) {
        char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        char[][] grid1 = {{'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'}};
        System.out.println(numIslands(grid1));
    }

    //提供方法          官方题解二：广度优先搜索  BFS
    //所有的1放入队列。依次出队并置为0
    //在循环里面bfs，bfs的次数即为岛屿数量
    public static int numIslands(char[][] grid) {
        //边缘
        if (grid.length == 0)
            return 0;

        //初始化
        int n = grid.length;
        int m = grid[0].length;
        int nums_island = 0;
        int temp=n*m;

        //所有的1放入队列中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    //岛屿数量先加1，先把找到的这个1置为0
                    nums_island++;
                    grid[i][j] = '0';

                    //BFS
                    Queue<Integer> queue = new LinkedList<>();
                    queue.add(i * temp + j);
                    while (!queue.isEmpty()) {
                        int id = queue.poll();
                        int row = id / temp;
                        int col = id % temp;
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            queue.add((row - 1) * temp + col);
                            grid[row - 1][col] = '0';
                        }
                        if (row + 1 < n && grid[row + 1][col] == '1') {
                            queue.add((row + 1) * temp + col);
                            grid[row + 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            queue.add(row * temp + (col - 1));
                            grid[row][col - 1] = '0';
                        }
                        if (col + 1 < m && grid[row][col + 1] == '1') {
                            queue.add(row * temp + (col + 1));
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }
        return nums_island;
    }
}
/*
给你一个由 ''1''（陆地）和 ''0''（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 '1':

输入:
'1''1''1''1''0'
'1''1''0''1''0'
'1''1''0''0''0'
'0''0''0''0''0'
输出: '1'
示例 2:

输入:
'1''1''0''0''0'
'1''1''0''0''0'
'0''0''1''0''0'
'0''0''0''1''1'
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */